
import java.util.*;

public class Solution {
    public String[] permutation(String s) {
        arr = s.toCharArray();
        Arrays.sort(arr);
        len = arr.length;
        used = new boolean[len];
        res = new ArrayList<>();
        path = new LinkedList<>();
        dfs(0);
        return res.toArray(new String[0]);

    }

    private char[] arr;
    private boolean[] used;
    private List<String> res;
    private int len;

    private List<Character> path;  // 这里更好是用 StringBuilder来模拟栈更好
    /*涉及到与字符串的相互转化只和char数组，stringbuilder有关系，其他类型都不太好转比如list*/
    public void dfs(int depth) {
        char[] temp = new char[len];
        if (depth == len) {
            for (int i = 0; i < len; i++) {
                temp[i] = path.get(i);
            }
            String str = String.valueOf(temp);
            res.add(str);
            return;
        }
        for (int i = 0; i < len; i++) {
            if (used[i] || (i > 0 && arr[i] == arr[i-1] && !used[i-1])) {
                continue;
            }
            used[i] = true;
            path.add(arr[i]);
            dfs(depth+1);
            path.remove(depth);
            used[i] = false;
        }
    }
}
